1. Field of the Invention
This invention relates generally to computers and memory devices, and, more particularly, to a method and apparatus to detect and correct soft errors in content addressable memory arrays.
2. Description of the Related Art
FIG. 1 illustrates one source of soft errors that occasionally occur during the storage or retrieval of binary information, i.e. impacts of cosmic rays and alpha particles on data storage devices. If a cosmic ray or alpha particle 10 crosses a memory location 12 of a semiconductor data storage device or array 14, the value of a binary bit 16 of data stored therein may be changed. The data storage device 14 of FIG. 1 may be a readable memory such as a random access memory. In the example of FIG. 1, the second bit 16 of the memory location 12 has value of logic 1 before the cosmic ray crosses the memory location 12, and the second bit 16 has the value of logic 0 after the cosmic ray 10 crosses therethrough. Several methods and apparatus have been devised to detect and correct the soft errors that occur while storing and retrieving binary data to and from readable memory devices like the data storage device 14 of FIG. 1. The methods and apparatus generally employ parity bits or error correction codes.
FIG. 1 illustrates how parity may be used to detect soft errors. Some prior art data storage arrays 14 have a parity memory bit 18 associated with each memory location 12 or possibly with each byte in the storage array 14. Each parity memory cell 18 has a value of logic 1 or 0 when the sum of the binary digits of the "original" data word stored in the associated memory location 12 is odd or even, respectively. Thus, the parity is equal to b.sub.0 .sym.b.sub.1 .sym.b.sub.2 .sym. . . . .sym.b.sub.n-1 where b.sub.j is the j-th bit of an n-bit memory location and .sym. indicates logical exclusive OR. In the usual case, the parity memory cells 18 associated with the data storage device 14 are collected in a separate bank of readable memory referred to as the parity memory 20.
The parity value of a data word is stored in the parity memory cell 18 at the same time that the data word is originally stored in the associated memory location 12. A cosmic ray or alpha particle ordinarily induces a single error in the data word at the memory location 12 without affecting the parity data stored in the parity memory cell 18. Thus, the parity of the data word at the memory location 12 and the parity stored in the parity memory cell 18 are ordinarily different after a single cosmic ray or alpha particle induces an error. The soft error is detected by comparing the parity of the data word to the original parity stored in the parity memory cell 18.
FIG. 2A illustrates a parity encoder 22 for determining the parity of a four bit data word 24. The logic signals from the first two bits 26, 28 of the data word 24 are sent to input terminals of a first, exclusive OR gate 30. The logical signals from the last two bits 32, 34 of the data word 24 are sent to input terminals of a second, exclusive OR gate 36. The output terminals of the first and second exclusive OR gates 30,36 are connected to a third exclusive OR gate 38. The output terminal 40 of the third exclusive OR gate 38 will deliver a signal representative of the parity of the input data word 24. The parity encoder 22 may be generalized to a device (not shown) that determines the parity of a data word of any length.
FIG. 2B illustrates a device 42 that employs a parity bit 44 to determine whether a soft one-bit error has occurred in a data word that of the data storage array 14. The parity bit 44 was stored in the parity memory cell at the same time that the original data word (not shown) was stored in the associated data memory location. The device 42 detects soft errors by reading both the data word 24 and the original parity bit 44. The data word is transmitted to the input terminals of the parity encoder 22. The original parity bit 44 may in some cases be stored by a delay element 46 while the parity encoder 22 processes the data word 24. The output terminals of the parity encoder 22 and the delay 46 are connected to the input terminals of an exclusive OR gate 48. The exclusive OR gate 48 acts like a parity comparator determining whether the data word 24 has been changed by a soft error. If the output terminal 50 produces a signal having the value logic 1, a soft error has occurred during either the storage or reading of the data word 24. If the output terminal 50 produces a signal having the value logic 0, the data word 24 does not contain a soft error. The error detector 42 enables the detection of soft errors only when the data word 24 is read.
Similar devices using multiple parity bits and error correction codes (not shown) may be employed to determine which bit of the data word 24 has been changed by the soft error. Nevertheless, the error detection apparatus of the prior art are designed to detect errors when the data words are read. Modern processors have data storage devices or arrays, typically built from static random access memory (SRAM cells), that contain data words which are never read explicitly. The detection of errors in data storage devices that are not read is outside the scope of the prior art device 42 of FIG. 2B.
FIG. 3 illustrates a content addressable memory (CAM) array 52. The CAM array 52 is used for comparisons between an input data word 54 and memory words stored in the CAM array 52, such as first and second memory words 56, 58. The CAM array 52 only produces "hit or match" signal on output lines 60, 62. Each bit of the memory words 56, 58, e.g., bits, 64, 66, 68, 70 of the first memory word 56, is connected to a first input terminal of an exclusive NOR gate in a bank of NOR gates, e.g., the bank contains the NOR gates 72, 74, 76, 78 for the first memory word 56 of the CAM array 52. The second input of each exclusive NOR gate, 72, 74, 76, 78 for the first memory word 56 receives an input logic signal from a single digit of the input data word 54. If all of the digits of the input data word 54 match one of the memory words 56 to 58 stored in the CAM array 52, the output line 60, 62 of an associated AND gate 80, 82 produces an output signal having the value of logic 1, indicating a "hit." When no output line, e.g., the output lines 60, 62 and output lines for other memory words (not shown) stored in the CAM array 52, produces a "hit" signal, the output signal of the CAM array 52 is referred to as a "miss" signal.
The memory words 56, 58 stored in the CAM array 52 are never read explicitly. Rather the memory words 56, 58 of the CAM array 52 are only used to produce output "hit or match" signals in response to matches with the input data word 54. Since the data words stored in memory locations 56, 58 are not read, an error detector such as the device 42 of FIG. 2B may not be employed to detect soft errors that have occurred in the CAM array 52. Nevertheless, soft errors may occur in a CAM array 52 due to the same causes for soft errors occurring in the readable data storage device 14 illustrated in FIG. 1, i.e. impacts of cosmic rays, alpha particles, etc.
CAM arrays are used in a variety of capacities in modern computers. For example, CAM arrays are used in look-up tables or directories associated with cache memories. Furthermore, the memory locations of modern CAM arrays have reduced capacitance's and operating voltages. Therefore, modern CAM arrays are more susceptible to the soft errors induced by alpha particles and cosmic rays. Because of the importance of CAM arrays in modern computers and processors, it is important to develop methods and apparatus for the detection of soft errors therein. Errors which are undetected could result in system failure or system data corruption.
The present invention is directed to overcoming, or at least reducing the effects of, one or more of the problems set forth above.